4142. Большой XOR

Для заданного целого числа x найдите количество таких целых чисел a, которые удовлетворяют условиям:

· a xor x > x

· 0 < a < x

где xor – битовый XOR оператор.

Имеются q запросов, каждый из которых содержит целое число x. Для каждого запроса выведите общее количество значений a, удовлетворяющих условиям выше.

Вход. Первая строка содержит число запросов q (1 ≤ q ≤ 10⁵). Каждая из следующих q строк содержит значение x (1 ≤ x ≤ 10¹⁰).

Выход. Для каждого теста выведите в отдельной строке количество значений a, удовлетворяющих приведенным условиям.

Пример входа	Пример выхода
2 2 10	1 5

РЕШЕНИЕ

математика

Анализ алгоритма

Рассмотрим двоичное представление числа x = b_kb_k-1…b₂b₁b₀. Если некоторое b_i равно 0, то на его месте можно поставить 1, а на позициях b_i-1…b₀ может находиться любое число. То есть при b_i = 0 любое значение a = 1b_i-1…b₀ нам подходит (a xor x > x, 0 < a < x). Таких возможных значений a имеется 2ⁱ.

Остается перебрать все позиции i, для которых b_i = 0 и просуммировать значения 2ⁱ.

Пример

Число x = 78 в двоичном представлении имеет вид 1001110.

Искомое количество значений а для x = 78 равно 1 + 16 + 32 = 49.

Реализация алгоритма

Читаем входные данные:.

scanf("%lld", &q);

while (q--)

{

scanf("%lld", &x);

res = 0;

В переменной i перебираем индексы битов числа x.

for (i = 0; x > 0; i++)

{

Если i-ый бит числа x равен 0, то к сумме прибавляем 2ⁱ.

if (x % 2 == 0) res += (1LL << i);

x /= 2;

}

Выводим ответ.

printf("%lld\n", res);

}